﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode
{
    class P0039 : IProblem
    {
        public void Run()
        {
            var s = new Solution();
            s.CombinationSum(new int[] { 2, 3, 6,7}, 7);
        }

        public class Solution
        {
            public static Dictionary<int, List<IList<int>>> m_map = new Dictionary<int, List<IList<int>>>();
            public static HashSet<int> m_set;
            public IList<IList<int>> CombinationSum(int[] candidates, int target)
            {
                var path = new List<int>();
                var pathList = new List<IList<int>>();

                Backtrack(candidates, 0, target, path, pathList);


                return pathList;
            }

            public void Backtrack(int[] candidates, int index, int target, IList<int> path, IList<IList<int>> res)
            {
                for (int i = index; i < candidates.Length; i++)
                {
                    var candidate = candidates[i];
                    path.Add(candidate);

                    //刚好等于
                    if (candidate == target)
                    {
                        res.Add(new List<int>(path));
                    }
                    //候选小于目标 如 2 < 7; 则需要继续向下决策
                    if (candidate < target)
                    {
                        Backtrack(candidates, i + 1, target - candidate, path, res);
                    }

                    //候选大于目标 则结束决策,向上回溯
                    if (candidate > target)
                    {

                    }
                    //结束时向上回溯
                    path.RemoveAt(path.Count - 1);

                }
            }
        }
    }
}
